package 递增子序列;

import java.util.*;

/**
 * @author: AirMan
 * @date: 2025/4/16 11:09
 * @description: 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
 * 示例:
 * 输入: [4, 6, 7, 7]
 * 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
 * 说明:
 * 给定数组的长度不会超过15。
 * 数组中的整数范围是 [-100,100]。
 * 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
 */
public class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 求子集问题，但是需要筛选一些树节点，仍然是采用回溯法
        // 回溯的参数：nums，
        // 回溯的返回值：void
        // 回溯的终止条件：startIndex >= nums.length
        // 单层回溯的逻辑：求子序列不需要将数组进行排序！
        // 横向遍历时，for就是开辟新的树枝，需要解决树层去重情况
        // 纵向遍历时，递归搜索不需要担心子集元素重复，因为题目讲述的是：如出现两个整数相等，也可以视作递增序列的一种特殊情况

        backtarcking(nums, 0);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public void backtarcking(int[] nums, int startIndex) {
        // 筛选树节点
        if (path.size() >= 2) {
            result.add(new ArrayList<>(path));
        }

        if (startIndex >= nums.length) {
            return;
        }

        Set<Integer> used = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {

            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i]
                    || used.contains(nums[i])) {
                continue;
            }

            used.add(nums[i]);
            path.add(nums[i]);
            backtarcking(nums, i + 1);
            path.removeLast();
        }

    }
}
